The simplest of hard optimization problems

... is for sure the problem of optimizing a quadratic function over a
polyhedron, at least from the continuous mathematics perspective.
Interestingly enough, this class can also model many discrete
optimization problems (which is not too surprising as, e.g., the
constraint x² = x models binarity of x).

In a bold attempt to combine four different aspects: (1) large-scale
applied problems; (2) a nice structural theory; (3) data analysis; and
(4) state-of-the-art optimization, this talk starts out with a topic
undeniably close to statistics: a relaxed clustering method via
dominant sets. This method has proved quite successful in recent
years, in Image Segmentation as well in many other fields, and
algorithmic implementations of this idea will lead us, as announced,
to the simplest quadratic optimization problem which is NP-hard,
namely minimizing a quadratic form over the standard simplex.

In turn, this so-called Standard Quadratic Problem (StQP) gives rise
to a nowadays popular domain in the interface of continuous and
discrete optimization, namely Copositive Optimization (COP). While in
the StQP formulation we face many (sub-optimal) local solutions, the
COP latter formulation has only one, as the objective and the
structural constraints are linear. Here, the whole complexity of the
problem is pushed to the membership constraint of the (closed and
convex) cone, which also shows that not all convex optimization
problems are equally easy. This talk will shortly review recent
advances in this young field, along with some applications.